package com.zjsru.leetcode75.level1.tree;

/**
 * @Author: cookLee
 * @Date: 2023-12-17
 * 二叉树中的最长交错路径
 * 选择二叉树中 任意 节点和一个方向（左或者右）。
 * 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 * 改变前进方向：左变右或者右变左。
 * 重复第二步和第三步，直到你在树中无法继续移动。
 */
public class LongestZigZag {

    /**
     * 主
     * \
     * 输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
     * 输出：3
     * 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
     * \
     * 输入：root = [1,1,1,null,1,null,null,1,1,null,1]
     * 输出：4
     * 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3, new TreeNode(9, null, null), new TreeNode(20, new TreeNode(15, null, null), new TreeNode(7, null, null)));
        LongestZigZag longestZigZag = new LongestZigZag();
        System.out.println(longestZigZag.longestZigZag(tree));
    }

    Integer ans = 0;

    /**
     * 最长之字形:深度优先搜索
     *
     * @param root 根
     * @return int
     */
    public int longestZigZag(TreeNode root) {
        if(root == null){
            return 0;
        }
        //使用广度优先搜索来遍历，参数分别为节点，初始计数和节点方向 1 表示往左遍历，2 表示往右遍历
        this.dfs(root.left,1,1);
        this.dfs(root.right,1,2);
        return ans;
    }

    /**
     * dfs
     *
     * @param root      根
     * @param count     计数
     * @param direction 方向
     */
    private void dfs(TreeNode root, int count, int direction) {
        if(root == null){
            return;
        }
        ans = Math.max(ans,count);
        //如果前一个方向是从左边来的(direction == 1)，那当前继续往左遍历的 count 从 1 开始计算
        //如果前一个方向是从右边来的(direction != 1)，那当前继续往左遍历的 count 加 1 继续计算
        this.dfs(root.left,direction == 1 ? 1 : count + 1, 1);

        //如果前一个方向是从右边来的(direction == 2)，那当前继续往右遍历的 count 从 1 开始计算
        //如果前一个方向是从左边来的(direction != 2)，那当前继续往右遍历的 count 加 1 继续计算
        this.dfs(root.right,direction == 2 ? 1 : count + 1, 2);
    }


}
